Genetic Algorithms and Applications
Fall 2023
MW 13:00-14:15

Course Outline: This course provides heuristic approach in optimization. It includes Genetic algorithms (GAs) and Tabu search. Genetic representation, selection, operators, niche, and parallelism are discussed in GAs. Tabu moves, tenure, aspiration criteria, short term and long term memories are examined in Tabu search. Theoretical improvements of the methods are examined for both the solution quality and computational complexity. Applications to various optimization problems are discussed.

   Professor

         Dr. Chae Young Lee
         Phone: (042) 350-2916
         Office: Room 4208 at E2-1
         Office hours: M W 9:30-11:00

   Teaching Assistant

         Joon Seok Im
         Phone: (042) 350-3116
         Office: Room 2113 at E2-2
         Office hours: T TH 14:30-16:00

    Grading

         Mid-term (25%) Date: 10/11
         Final (25%) Date: 12/6
         Homework (10%)
         Paper presentation (20%)
         Term project (20%)

    The Texts

        Genetic Algorithms, by Goldberg, Addison Wesley, 1989
        Tabu Search, by Glover and Laguna, Kluwer Academic Publishers, 1997

   

Schedule

Date	Topics	Read
8/28	Introduction to GAs	Chap. 1
8/30	What is GA? A GA by hand
9/4	Schemata, Schema theorem	Chap. 2
9/6	Implicit parallelism, Building block hypothesis	P1, P2
9/11	Deception, Decision making
9/13	A simple GA in Pascal	Chap. 3
9/18	Selection schemes	Chap. 4
9/20	Selection schemes	P3
9/25	Parallel GAs	P4
9/27	Selection schemes	P5
10/2	Order-Based GAs, Graph Coloring Problem
10/4	Reordering, Inversion operator	Chap. 5
10/11	Mid-term Exam
10/23	Real code representation	P6, P7, P8, P9
10/25	Niching, Crowding, Sharing	Chap. 5
10/30	Nitching	P10, P11
11/1	Dominance, Diploidy	Chap. 5
11/6, 8	Convergence and Diversity	P12
11/13,	Introduction to Tabu Search	Chap. 1, P13
11/15	Short term memory	Chap. 2, 3
11/20	Long term memory	Chap. 4
11/22	Parametric Tabu Search	P14
11/27	Presentation of term projects
11/29	Presentation of term projects
12/4	Presentation of term projects
12/6	Final Exam

 Paper Reading List

[P1] Mitchel, M. and Forrest, S., Relative Building Block Fitness and Building-Block Hypothesis, Proceedings of Foundations of GAs, 109-126, 1992.

[P2] Mitchel, M., Royal Roads, 127-138, An Introduction to GAs, The MIT Press, 1996.

[P3] Goldberg D.E., A Comparative Analysis of Selection Schemes used in Genetic Algorithms, Proceedings of Foundations of GAs, 69-93 1991.

[P4] Gordon, S. and Whitley, D., Serial and Parallel Genetic Algorithms as Function Optimizer, Proceedings of 5th International Conference on GAs, 177-183, 1993.

[P5] De Jong, K and Sarma, J, On Decentralizing Selection Algorithms, Proceedings of 6^th ICGA, 9-16, 1995.

[P6] Eshelman, L.J. and Schaffer, J.D., Real-Coded Genetic Algorithms and Interval-Schemata, Proceedings of Foundations of GAs, 187-202, 1993

[P7] Mathias, K.E. and Whitley, D., Changing Representation During Search: A Comparative Study of Delta Coding, Evolutionary Computation, 2(3), 249-278, 1994.

[P8] Falkenauer, E., A New Representation and Operators for Genetic Algorithms Applied to Grouping Problems, Evolutionary Computation, 2(2), 123-144, 1994.

[P9] Tucker, Allan et al., RGFGA: An Efficient Representation and Crossover for Grouping Genetic Algorithms, Evolutionary Computation 13(4), 477-499, 2005.

[P10] Mahfoud, S.W., A Comparison of Parallel and Sequential Niching Methods, Proceedings of 6^th ICGA, 136-143, 1995.

[P11] Horn, J. and Goldberg, D.E.,Toward a Control Map for Nitching, Proceedings of Foundations of GAs, 287-310, 1999

[P12] Laumanns, M. et al., Combining Convergence and Diversity in Evolutionary Multiobjective Optimization, Evolutionary Computation 10(3), 263-282, 2002.

[P13] Glover, F., Tabu Search: A Tutorial, Interfaces, 20(4), 74-94, 1990.

[P14] Glover, F., Parametric Tabu Search for Mixed Integer Programs, Computers and Operations Research, 33, 32449-2494, 2006.